package com.example.algorithm.selectionsort;

/**
 * 选择排序：
 *      从数组开头开始往后寻找，找到最小的元素，将其放到数组开始
 *      从剩余的元素中继续寻找最小的元素，将其放到上次最小的元素后面
 */
public class SelectionSort {

    private SelectionSort() {}

    /**
     * 循环不变量分析：
     *      arr[i ... n) 未排序，
     *      arr[0 ... i) 已排序
     *  维护循环不变量：
     *      arr[i .. n) 中的最小值要放到 arr[i] 的位置
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int n = i; n < arr.length; n++) {
                if (arr[n].compareTo(arr[minIndex]) < 0) {
                    minIndex = n;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    private static <E> void swap(E[] arr, int idx1, int idx2) {
        E tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

}
